package gold.digger;

import gold.vo.ListNode;

import java.util.Stack;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC25 {



    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        if (k <= 1) {
            return head;
        }

        Stack<ListNode> st = new Stack<>();
        ListNode cur = head;
        for (int i = 0; i < k - 1; ++i) {
            if (cur == null) {
                return head;
            }
            st.push(cur);
            cur = cur.next;
        }

        // reverse the list
        if (cur == null) {
            return head;
        }

        ListNode reverseHead = cur;
        ListNode nextReverseHead = reverseKGroup(cur.next, k);
        for (int i = 0; i < k - 1; ++i) {
            cur.next = st.pop();
            cur = cur.next;
        }

        cur.next = nextReverseHead;
        return reverseHead;
    }

    public void testMethod() {
        LC25 an = new LC25();
        ListNode h1 = new ListNode(1);
        h1.next = new ListNode(2);
        h1.next.next = new ListNode(3);
        h1.next.next.next = new ListNode(4);
        h1.next.next.next.next = new ListNode(5);
//        h1.next.next.next.next.next = new ListNode(6);

        System.out.println(an.reverseKGroup(h1, 2));
    }

    public static void main(String[] args) {
        LC25 an = new LC25();
        an.testMethod();
    }
}
